package com.wjw.java.collection.set_;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * HashSet是Set接口的实现类：
 * -------------------------------------------------------------------------
 * HashSet细节：
 * 1.HashSet是无序的(没有索引),不能保存重复元素的集合
 * 2.可以保存有且只有一个null
 * 3.底层是一个哈希表结构HashMap(底层是数组+链表+红黑树)
 *   public HashSet() {
 *      map = new HashMap<>();
 *   }
 * -------------------------------------------------------------------------
 * 底层源码分析：
 * 1.HastSet底层就是HashMap(底层是数组+链表+红黑树)
 * 2.添加一个元素时,先得到hash值,然后将hash值转为索引值,及数组的索引是hash值
 * 3.找到存储数据表table,看这个索引位置是否已经存在元素
 * 4.如果没有,直接加入
 * 5.如果有,调用equal方法比较,如果相同就放弃添加,如果不同,则添加到最后
 * 6.在Java8中,如果一条链表的元素个数超过8,并且table的大小 >= 64就会转为红黑树
 * -------------------------------------------------------------------------
 * Hashset扩容和转成红黑树机制：
 * 1.HastSet底层就是HashMap,第一次添加时,table大小扩容到16,临界值 = 16 * 0.75(加载因子) = 12
 * 2.如果table数组使用到了临界值12,就会扩容到16 * 2 = 32,新的临界值 = 32 * 0.75(加载因子) = 24
 * 3.如果一条链表table上的元素个数达到8,并且talbe的大小 >= 64,就会转为红黑树,否则还是采用数组的扩容机制
 * 4.只要往Hashset中添加一个元素,size就会++,添加到不同table上,size达到临界点,就会触发扩容!!!
 *   而非必须在同一个table上,才会触发扩容!!!
 * -------------------------------------------------------------------------
 */
public class Detail_HashSet {
    public static void main(String[] args) {
        //hashset_distinct();
        //hashset_structure();
        hashset_increment();
    }
    //1.使用HashSet去重
    public static void hashset_distinct(){
        Set set = new HashSet();
        set.add("wjw");//添加成功
        set.add("wjw");//添加失败
        set.add(new String("dw"));//添加成功
        set.add(new String("dw"));//添加失败
        set.add(new Dog("大黄狗",3));//添加成功
        set.add(new Dog("大黄狗",3));//添加成功
        System.out.println(set);
    }

    /**
     * 2.HashSet的底层是HashMap,现在模拟一个简单的HashMap底层
     * ----------------------------------------------------------------------------------
     * 数组+链表结构如下：数组的每一个下标都可以放一个Node,该Node下又可以放Node...从而形成链表
     * ----------------------------------------------------------------------------------
     * table[0]
     *
     * (Node)          (Node)         (Node)
     * next    -->     next    -->     next
     * item            item            item
     *
     * table[1]
     *
     * (Node)
     * next    -->     null
     * item
     *
     * ...
     *
     * ----------------------------------------------------------------------------------
     */
    public static void hashset_structure(){
        //创建一个Node类型的数组,有些人直接把Node[]称为表
        Node [] table = new Node[16];
        //创建1个Node
        Node n1 = new Node("N1",null);
        //将n1放在table[0]的位置上,n2在n1后,n3在n2后
        table[0] = n1;
        Node n2 = new Node("N2",null);
        n1.next = n2;
        Node n3 = new Node("N3",null);
        n2.next = n3;
        System.out.println(Arrays.toString(table));
        //将n4放在table[1]的位置上,
        Node n4= new Node("N4",null);
        table[1] = n4;
        System.out.println(Arrays.toString(table));
    }

    /**
     * 3.Hashset扩容演示,及转为红黑树演示
     */
    public static void hashset_increment(){

        /**
         * Hashset扩容演示,使用debug查看变化:
         * -----------------------------------------------------
         * 第1次新增元素时,table默认大小为16,
         * threshold临界值为12
         * loadFactor加载因子为0.75
         * ...
         * 第13次新增元素时,超过临界值12,table大小扩容到16 * 2 = 32
         * threshold临界值为32 * 0.75 = 24
         * ...
         * 第25次新增元素时,超过临界值24,table大小扩容到32* 2 = 64
         * threshold临界值为64 * 0.75 = 48
         * ...
         * 第49次新增元素时,超过临界值48,table大小扩容到64* 2 = 128
         * threshold临界值为128 * 0.75 = 96
         * ...
         * 因为他们的hashcode值不同,没挂在同一个table上,所有没有转为红黑树
         */
        HashSet set = new HashSet();
        for (int i = 1; i <= 100; i++) {
            set.add(i);
        }

        /**
         * Hashset扩容转为红黑树演示,使用debug查看变化:
         * 因为A类重写了hashCode方法,返回的hashCode值都是100,
         * 所以新增时,会往同一个table[]数组上添加元素,
         * 及在同一个table的next上添加元素,next,next...
         * -----------------------------------------------------
         * i = 1时,table默认大小为16
         * threshold临界值为12
         * loadFactor加载因子为0.75
         * i = 9时,table扩容至32,临界值 = 16 * 2 * 0.75 = 24
         * i = 10时,table扩容至64,临界值 = 32 * 2 * 0.75 = 48
         * i = 11时,满足table[]转为红黑树条件
         * 该table上的元素有8个(此刻11个),且table的大小 >= 64
         */
        HashSet set2 = new HashSet();
        for (int i = 1; i <= 12; i++) {
            set2.add(new A(i));
        }

        //只要往Hashset中添加一个元素,size就会++,添加到不同table上,size达到临界点,就会触发扩容!!!
        //而非必须在同一个table上,才会触发扩容!!!
        HashSet set3 = new HashSet();
        for (int i = 1; i <= 7; i++) {
            set3.add(new A(i));
        }
        for (int i = 1; i <= 7; i++) {
            set3.add(new B(i));
        }
    }
}

//节点类,存储数据,可以执行下一个节点,从而形成链表
class Node{
    public Object item;//用于保存数据
    public Node next;//指向下一个节点
    public Node() {
    }
    public Node(Object item, Node next) {
        this.item = item;
        this.next = next;
    }
    @Override
    public String toString() {
        return "Node{" +
                "item=" + item +
                ", next=" + next +
                '}';
    }
}

//重写Dog类的hashCode方法和equals方法,放入HashSet集合中去重
class Dog{
    private String name;
    private int age;

    public String getName() {
        return this.name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public int getAge() {
        return this.age;
    }
    public void setAge(int age) {
        this.age = age;
    }
    public Dog() {
    }
    public Dog(String name, int age) {
        this.name = name;
        this.age = age;
    }
    @Override
    public String toString() {
        return "Dog{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

//重写该类的hashCode,让new出来的对象的hashCode值相等,
//放入Hashset集合中时,就会保存在同一个table上,
//当该table的大小为8时,在添加元素时,会将table大小扩容到32
//再次添加元素时,table就会扩容到64,此时满足table数组转为红黑树的条件
//会将该table转为红黑树
class A{
    private int n;

    public A(int n) {
        this.n = n;
    }

    @Override
    public int hashCode() {
        return 100;
    }
}
//同上
class B{
    private int m;

    public B(int m) {
        this.m = m;
    }

    @Override
    public int hashCode() {
        return 200;
    }
}